import java.util.HashMap;
import java.util.Map;

/**
 * 面试题67：把字符串转换成整数
 */
public class Offer_67 {
    /**
     * 标记输入是否合法，true 为合法，false 为非法
     */
    boolean validInput = true;

    /**
     * 方法一：一次遍历
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(1)
     */
    public int strToInt(String str) {
        // 输入为 null，非法输入
        if (str == null) {
            validInput = false;
            return 0;
        }

        int len = str.length();
        // 空字符串，非法输入
        if (len == 0) {
            validInput = false;
            return 0;
        }

        int index = 0;
        // 1. 忽略前导空格
        while (index < len && str.charAt(index) == ' ') {
            index++;
        }
        // 2. 如果字符串只包含空格，非法输入
        if (index == len) {
            validInput = false;
            return 0;
        }

        // 3. 检查第一个字符是否是正负号
        int sign = 1;
        char firstChar = str.charAt(index);
        if (firstChar == '+') {
            index++;
        } else if (firstChar == '-') {
            sign = -1;
            index++;
        }

        int ans = 0;
        // 4. 遍历字符
        while (index < len) {
            char curChar = str.charAt(index);
            // 如果当前字符不是数字字符，非法输入
            if (curChar < '0' || curChar > '9') {
                validInput = false;
                break;
            }
            // 根据题目要求，上下溢出返回相应值
            if (ans > Integer.MAX_VALUE / 10
                    || (ans == Integer.MAX_VALUE / 10 && (curChar - '0') > Integer.MAX_VALUE % 10)) {
                return Integer.MAX_VALUE;
            }
            if (ans < Integer.MIN_VALUE / 10
                    || (ans == Integer.MIN_VALUE / 10 && (curChar - '0') > -(Integer.MIN_VALUE % 10))) {
                return Integer.MIN_VALUE;
            }
            // 合法，进行计算
            // 每一步都把符号位乘进去，因为还要比较下溢出
            ans = ans * 10 + sign * (curChar - '0');
            index++;
        }
        return ans;
    }

    /**
     * 方法二：确定有限状态自动机
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(1)
     */
    public int myAtoi(String str) {
        Automaton automaton = new Automaton();
        int len = str.length();
        for (int i = 0; i < len; i++) {
            automaton.get(str.charAt(i));
        }
        return (int) (automaton.sign * automaton.ans);
    }
}

class Automaton {
    public int sign = 1;
    public long ans = 0;
    private String state = "start";
    private Map<String, String[]> table = new HashMap<>() {
        {
            put("start", new String[] { "start", "signed", "in_number", "end" });
            put("signed", new String[] { "end", "end", "in_number", "end" });
            put("in_number", new String[] { "end", "end", "in_number", "end" });
            put("end", new String[] { "end", "end", "end", "end" });
        }
    };

    public void get(char c) {
        state = table.get(state)[getCol(c)];
        if ("in_number".equals(state)) {
            ans = ans * 10 + (c - '0');
            if (sign == 1) {
                ans = Math.min(ans, (long) Integer.MAX_VALUE);
            } else {
                ans = Math.min(ans, -(long) Integer.MIN_VALUE);
            }
        } else if ("signed".equals(state)) {
            if (c == '+') {
                sign = 1;
            } else {
                sign = -1;
            }
        }
    }

    private int getCol(char c) {
        if (c == ' ') {
            // 0 为 start
            return 0;
        }
        if (c == '+' || c == '-') {
            // 1 为 signed
            return 1;
        }
        if (Character.isDigit(c)) {
            // 2 为 in_number
            return 2;
        }
        // 3 为 end
        return 3;
    }
}
